package com.bee.剑指offer;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。
 * 其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。
 * 每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，
 * 从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，
 * 并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？
 */
public class 孩子们的游戏圆圈中最后剩下的数 {

    /**
     * 使用队列就能解决，
     * 先将元素所有都压入队列中，之后遍历队列，将步骤为3的元素进行poll，不等于步骤的直接加入到队列尾部
     */
    public static int LastRemaining_Solution(int n, int m) {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i);
        }
        int count = 1;
        while (true) {
            if(queue.size() == 1) {
                return queue.peek();
            }
            if(count == m) {
                queue.poll();
                count = 1;
            } else {
                queue.offer(queue.poll());
                count++;
            }
        }
    }

    public static int latsRemain(int n, int m) {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.offer(i);
        }
        int count = 1;
        while (true) {
            if(queue.size() == 1) {
                return queue.peek();
            }
            if(count == m) {
                queue.poll();
                count = 1;
            } else {
                queue.offer(queue.poll());
                count++;
            }
        }
    }

    public static void main(String[] args) {
        int i = LastRemaining_Solution(5, 2);
        System.out.println(i);
    }
}
